package com.gitee.wsl.collections.list

import com.gitee.wsl.base.Objects
import com.gitee.wsl.base.Objects.equals
import com.gitee.wsl.collections.iterator.api.OrderedIterator
import kotlinx.io.IOException
import kotlin.jvm.Transient

/**
 * An abstract implementation of a linked list which provides numerous points for
 * subclasses to override.
 *
 *
 * Overridable methods are provided to change the storage node and to change how
 * nodes are added to and removed. Hopefully, all you need for unusual subclasses
 * is here.
 *
 *
 *
 * This is a copy of AbstractLinkedList, modified to be compatible with Java 21
 * (see COLLECTIONS-842 for details).
 *
 *
 * @param <E> the type of elements in this list
 * @see AbstractLinkedList
 *
 * @since 4.5.0-M3
</E> */
abstract class AbstractLinkedList<E> : MutableList<E> {
    /*
         * Implementation notes:
         * - a standard circular doubly-linked list
         * - a marker node is stored to mark the start and the end of the list
         * - node creation and removal always occurs through createNode() and
         *   removeNode().
         * - a modification count is kept, with the same semantics as
         * {@link java.util.LinkedList}.
         * - respects {@link AbstractList#modCount}
         */
    /**
     * A list iterator over the linked list.
     *
     * @param <E> the type of elements in this iterator.
    </E> */
    protected open class LinkedListIterator<E>(
        /** The parent list  */
        protected val parent: AbstractLinkedList<E>,
        /**
         * The index of [.next].
         */
        protected var nextIndex: Int,
    ) : MutableListIterator<E>, OrderedIterator<E> {
        /**
         * The node that will be returned by [.next]. If this is equal
         * to [AbstractLinkedList.header] then there are no more values to return.
         */
        protected var next: Node<E>

        /**
         * The last node that was returned by [.next] or [ ][.previous]. Set to `null` if [.next] or [ ][.previous] haven't been called, or if the node has been removed
         * with [.remove] or a new node added with [.add].
         * Should be accessed through [.getLastNodeReturned] to enforce
         * this behavior.
         */
        protected var current: Node<E>? = null

        /**
         * The modification count that the list is expected to have. If the list
         * doesn't have this count, then a
         * [ConcurrentModificationException] may be thrown by
         * the operations.
         */
        protected var expectedModCount: Int = parent.modCount

        /**
         * Create a ListIterator for a list.
         *
         * @param parent  the parent list
         * @param nextIndex  the index to start at
         * @throws IndexOutOfBoundsException if fromIndex is less than 0 or greater than the size of the list
         */
        init {
            this.next = parent.getNode(nextIndex, true)
        }

        override fun add(element: E) {
            checkModCount()
            parent.addNodeBefore(next, element)
            current = null
            nextIndex++
            expectedModCount++
        }

        /**
         * Checks the modification count of the list is the value that this
         * object expects.
         *
         * @throws ConcurrentModificationException If the list's modification
         * count isn't the value that was expected.
         */
        protected fun checkModCount() {
            if (parent.modCount != expectedModCount) {
                throw ConcurrentModificationException()
            }
        }

        @get:Throws(IllegalStateException::class)
        protected val lastNodeReturned: Node<E>
            /**
             * Gets the last node returned.
             *
             * @return the last node returned
             * @throws IllegalStateException If [.next] or [.previous] haven't been called,
             * or if the node has been removed with [.remove] or a new node added with [.add].
             */
            get() {
                checkNotNull(current)
                return current!!
            }

         override fun hasNext(): Boolean {
            return next != parent.header
        }

        override fun hasPrevious(): Boolean {
            return next.previous != parent.header
        }

         override fun next(): E {
            checkModCount()
            if (!hasNext()) {
                throw NoSuchElementException("No element at index $nextIndex.")
            }
            val value = next.value
            current = next
            next = next.next!!
            nextIndex++
            return value!!
        }

         override fun nextIndex(): Int {
            return nextIndex
        }

        override fun previous(): E {
            checkModCount()
            if (!hasPrevious()) {
                throw NoSuchElementException("Already at start of list.")
            }
            next = next.previous!!
            val value = next.value
            current = next
            nextIndex--
            return value!!
        }

         override fun previousIndex(): Int {
            // not normally overridden, as relative to nextIndex()
            return nextIndex() - 1
        }

         override fun remove() {
            checkModCount()
            if (current === next) {
                // remove() following previous()
                next = next.next!!
                parent.removeNode(this.lastNodeReturned)
            } else {
                // remove() following next()
                parent.removeNode(this.lastNodeReturned)
                nextIndex--
            }
            current = null
            expectedModCount++
        }

         override fun set(element: E) {
            checkModCount()
            this.lastNodeReturned.value = element
        }
    }

    /**
     * The sublist implementation for AbstractLinkedListJava21.
     *
     * @param <E> the type of elements in this list.
    </E> */
    protected open class LinkedSubList<E>(
        parent: AbstractLinkedList<E>,
        fromIndex: Int,
        toIndex: Int,
    ) : AbstractMutableList<E>() {
        /** The main list  */
        var parent: AbstractLinkedList<E>

        /** Offset from the main list  */
        var offset: Int

        /** Sublist size  */
        override var size: Int = 0

        /** Sublist modCount  */
        var expectedModCount: Int

        /**
         * Constructs a new instance.
         *
         * @param parent The parent AbstractLinkedList.
         * @param fromIndex An index greater or equal to 0 and less than `toIndex`.
         * @param toIndex An index greater than `fromIndex`.
         */
        init {
            if (fromIndex < 0) {
                throw IndexOutOfBoundsException("fromIndex = $fromIndex")
            }
            if (toIndex > parent.size) {
                throw IndexOutOfBoundsException("toIndex = $toIndex")
            }
            require(fromIndex <= toIndex) { "fromIndex($fromIndex) > toIndex($toIndex)" }
            this.parent = parent
            this.offset = fromIndex
            this.size = toIndex - fromIndex
            this.expectedModCount = parent.modCount
        }

         override fun add(index: Int, element: E) {
            rangeCheck(index, size + 1)
            checkModCount()
            parent.add(index + offset, element)
            expectedModCount = parent.modCount
            size++
            modCount++
        }

         override fun addAll(elements: Collection< E>): Boolean {
            return addAll(size, elements)
        }

         override fun addAll(index: Int, elements: Collection< E>): Boolean {
            rangeCheck(index, size + 1)
            val cSize: Int = elements.size
            if (cSize == 0) {
                return false
            }

            checkModCount()
            parent.addAll(offset + index, elements)
            expectedModCount = parent.modCount
            size += cSize
            modCount++
            return true
        }

        /**
         * Throws a [ConcurrentModificationException] if this instance fails its concurrency check.
         */
        protected fun checkModCount() {
            if (parent.modCount != expectedModCount) {
                throw ConcurrentModificationException()
            }
        }

         override fun clear() {
            checkModCount()
            val it = iterator()
            while (it.hasNext()) {
                it.next()
                it.remove()
            }
        }

         override fun get(index: Int): E {
            rangeCheck(index, size)
            checkModCount()
            return parent.get(index + offset)
        }

         override fun iterator(): MutableIterator<E> {
            checkModCount()
            return parent.createSubListIterator(this)
        }

         override fun listIterator(index: Int): MutableListIterator<E> {
            rangeCheck(index, size + 1)
            checkModCount()
            return parent.createSubListListIterator(this, index)
        }

        /**
         * Throws an [IndexOutOfBoundsException] if the given indices are out of bounds.
         *
         * @param index lower index.
         * @param beyond upper index.
         */
        protected fun rangeCheck(index: Int, beyond: Int) {
            if (index < 0 || index >= beyond) {
                throw IndexOutOfBoundsException("Index '$index' out of bounds for size '$size'")
            }
        }

        override fun removeAt(index: Int): E {
            rangeCheck(index, size)
            checkModCount()
            val result = parent.removeAt(index + offset)
            expectedModCount = parent.modCount
            size--
            modCount++
            return result!!
        }

         override fun set(index: Int, element: E): E {
            rangeCheck(index, size)
            checkModCount()
            return parent.set(index + offset, element)
        }



//        fun size(): Int {
//            checkModCount()
//            return size
//        }

         override fun subList(fromIndex: Int, toIndex: Int): MutableList<E> {
            return LinkedSubList(parent, fromIndex + offset, toIndex + offset)
        }
    }

    /**
     * A list iterator over the linked sub list.
     *
     * @param <E> the type of elements in this iterator.
    </E> */
    protected open class LinkedSubListIterator<E>(
        /** The sub list  */
        protected val sub: LinkedSubList<E>,
        startIndex: Int,
    ) : LinkedListIterator<E>(
        sub.parent, startIndex + sub.offset
    ) {
        override fun add(element: E) {
            super.add(element)
            sub.expectedModCount = parent.modCount
            sub.size++
        }

        override fun hasNext(): Boolean {
            return nextIndex() < sub.size
        }

        override fun hasPrevious(): Boolean {
            return previousIndex() >= 0
        }

        override fun nextIndex(): Int {
            return super.nextIndex() - sub.offset
        }

        override fun remove() {
            super.remove()
            sub.expectedModCount = parent.modCount
            sub.size--
        }
    }

    /**
     * A node within the linked list.
     *
     *
     * From Commons Collections 3.1, all access to the `value` property
     * is via the methods on this class.
     *
     *
     * @param <E> the type of the node value.
    </E> */
    open class Node<E> {
        /** A pointer to the node before this node  */
        var previous: Node<E>? = null

        /** A pointer to the node after this node  */
        var next: Node<E>? = null
        /**
         * Gets the value of the node.
         *
         * @return the value
         * @since 3.1
         */
        /**
         * Sets the value of the node.
         *
         * @param value  the value
         * @since 3.1
         */
        /** The object contained within this node  */
        var value: E? = null

        /**
         * Constructs a new header node.
         */
        constructor() {
            previous = this
            next = this
        }

        /**
         * Constructs a new node.
         *
         * @param value  the value to store
         */
        constructor(value: E) {
            this.value = value
        }

        /**
         * Constructs a new node.
         *
         * @param previous  the previous node in the list
         * @param next  the next node in the list
         * @param value  the value to store
         */
        protected constructor(previous: Node<E>, next: Node<E>, value: E?) {
            this.previous = previous
            this.next = next
            this.value = value
        }

        protected var nextNode: Node<E>
            /**
             * Gets the next node.
             *
             * @return the next node
             * @since 3.1
             */
            get() = next!!
            /**
             * Sets the next node.
             *
             * @param next  the next node
             * @since 3.1
             */
            set(next) {
                this.next = next
            }

        protected var previousNode: Node<E>
            /**
             * Gets the previous node.
             *
             * @return the previous node
             * @since 3.1
             */
            get() = previous!!
            /**
             * Sets the previous node.
             *
             * @param previous  the previous node
             * @since 3.1
             */
            set(previous) {
                this.previous = previous
            }
    }

    /**
     * A [Node] which indicates the start and end of the list and does not
     * hold a value. The value of `next` is the first item in the
     * list. The value of `previous` is the last item in the list.
     */
    @Transient
    lateinit var header: Node<E>

    /** The size of the list  */
    @Transient
    override var size: Int = 0

    /** Modification count for iterators  */
    @Transient
    var modCount: Int = 0

    /**
     * Constructor that does nothing (intended for deserialization).
     *
     *
     * If this constructor is used by a serializable subclass then the init()
     * method must be called.
     */
    protected constructor()

    /**
     * Constructs a list copying data from the specified collection.
     *
     * @param coll  the collection to copy
     */
    protected constructor(coll: Collection<E>) {
        init()
        addAll(coll)
    }

     override fun add(element: E): Boolean {
        addLast(element)
        return true
    }

     override fun add(index: Int, element: E) {
        val node = getNode(index, true)
        addNodeBefore(node, element)
    }

     override fun addAll(elements: Collection<E>): Boolean {
        return addAll(size, elements)
    }

     override fun addAll(index: Int, elements: Collection< E>): Boolean {
        val node = getNode(index, true)
        for (e in elements) {
            addNodeBefore(node, e)
        }
        return true
    }

    /**
     * {@inheritDoc}
     */
    fun addFirst(o: E) {
        addNodeAfter(header, o)
    }

    /**
     * {@inheritDoc}
     */
    fun addLast(o: E) {
        addNodeBefore(header, o)
    }

    /**
     * Inserts a new node into the list.
     *
     * @param nodeToInsert  new node to insert
     * @param insertBeforeNode  node to insert before
     * @throws NullPointerException if either node is null
     */
    protected fun addNode(nodeToInsert: Node<E>, insertBeforeNode: Node<E>) {
        nodeToInsert.next = insertBeforeNode
        nodeToInsert.previous = insertBeforeNode.previous
        insertBeforeNode.previous!!.next = nodeToInsert
        insertBeforeNode.previous = nodeToInsert
        size++
        modCount++
    }

    /**
     * Creates a new node with the specified object as its
     * `value` and inserts it after `node`.
     *
     *
     * This implementation uses [.createNode] and
     * [.addNode].
     *
     * @param node  node to insert after
     * @param value  value of the newly added node
     * @throws NullPointerException if `node` is null
     */
    protected fun addNodeAfter(node: Node<E>, value: E) {
        val newNode = createNode(value)
        addNode(newNode, node.next!!)
    }

    /**
     * Creates a new node with the specified object as its
     * `value` and inserts it before `node`.
     *
     *
     * This implementation uses [.createNode] and
     * [.addNode].
     *
     * @param node  node to insert before
     * @param value  value of the newly added node
     * @throws NullPointerException if `node` is null
     */
    protected fun addNodeBefore(node: Node<E>, value: E) {
        val newNode = createNode(value)
        addNode(newNode, node)
    }

     override fun clear() {
        removeAllNodes()
    }

     override fun contains(element: E): Boolean {
        return indexOf(element) != -1
    }

     override fun containsAll(elements: Collection<E>): Boolean {
        for (o in elements) {
            if (!contains(o)) {
                return false
            }
        }
        return true
    }

    /**
     * Creates a new node with previous, next and element all set to null.
     * This implementation creates a new empty Node.
     * Subclasses can override this to create a different class.
     *
     * @return  newly created node
     */
    protected fun createHeaderNode(): Node<E> {
        return Node()
    }

    /**
     * Creates a new node with the specified properties.
     * This implementation creates a new Node with data.
     * Subclasses can override this to create a different class.
     *
     * @param value  value of the new node
     * @return a new node containing the value
     */
    protected fun createNode(value: E): Node<E> {
        return Node(value)
    }

    /**
     * Creates an iterator for the sublist.
     *
     * @param subList  the sublist to get an iterator for
     * @return a new iterator on the given sublist
     */
    protected fun createSubListIterator(subList: LinkedSubList<E>): MutableListIterator<E> {
        return createSubListListIterator(subList, 0)
    }

    /**
     * Creates a list iterator for the sublist.
     *
     * @param subList  the sublist to get an iterator for
     * @param fromIndex  the index to start from, relative to the sublist
     * @return a new list iterator on the given sublist
     */
    protected fun createSubListListIterator(subList: LinkedSubList<E>, fromIndex: Int): MutableListIterator<E> {
        return LinkedSubListIterator(subList, fromIndex)
    }

    /**
     * Deserializes the data held in this object to the stream specified.
     *
     *
     * The first serializable subclass must call this method from
     * `readObject`.
     *
     * @param inputStream  the stream to read the object from
     * @throws IOException  if any error occurs while reading from the stream
     * @throws ClassNotFoundException  if a class read from the stream cannot be loaded
     */
//    @Throws(IOException::class, ClassNotFoundException::class)
//    protected fun doReadObject(inputStream: ObjectInputStream) {
//        init()
//        val size: Int = inputStream.readInt()
//        for (i in 0..<size) {
//            add(inputStream.readObject() as E?)
//        }
//    }

    /**
     * Serializes the data held in this object to the stream specified.
     *
     *
     * The first serializable subclass must call this method from
     * `writeObject`.
     *
     * @param outputStream  the stream to write the object to
     * @throws IOException  if anything goes wrong
     */
//    @Throws(IOException::class)
//    protected fun doWriteObject(outputStream: ObjectOutputStream) {
//        // Write the size so we know how many nodes to read back
//        outputStream.writeInt(size())
//        for (e in this) {
//            outputStream.writeObject(e)
//        }
//    }

    override fun equals(obj: Any?): Boolean {
        if (obj === this) {
            return true
        }
        if (obj !is List<*>) {
            return false
        }
        val other = obj as List<*>
        if (other.size != size) {
            return false
        }
        val it1: ListIterator<*> = listIterator()
        val it2 = other.listIterator()
        while (it1.hasNext() && it2.hasNext()) {
            if (!Objects.equals(it1.next(), it2.next())) {
                return false
            }
        }
        return !(it1.hasNext() || it2.hasNext())
    }

     override fun get(index: Int): E {
        val node = getNode(index, false)
        return node.value!!
    }

    val first: E?
        /**
         * {@inheritDoc}
         */
        get() {
            val node = header.next!!
            if (node === header) {
                throw NoSuchElementException()
            }
            return node.value
        }

    val last: E?
        /**
         * {@inheritDoc}
         */
        get() {
            val node= header.previous!!
            if (node === header) {
                throw NoSuchElementException()
            }
            return node.value
        }

    /**
     * Gets the node at a particular index.
     *
     * @param index  the index, starting from 0
     * @param endMarkerAllowed  whether or not the end marker can be returned if
     * startIndex is set to the list's size
     * @return the node at the given index
     * @throws IndexOutOfBoundsException if the index is less than 0; equal to
     * the size of the list and endMakerAllowed is false; or greater than the
     * size of the list
     */
    @Throws(IndexOutOfBoundsException::class)
    protected fun getNode(index: Int, endMarkerAllowed: Boolean): Node<E> {
        // Check the index is within the bounds
        if (index < 0) {
            throw IndexOutOfBoundsException(
                "Couldn't get the node: " +
                        "index (" + index + ") less than zero."
            )
        }
        if (!endMarkerAllowed && index == size) {
            throw IndexOutOfBoundsException(
                "Couldn't get the node: " +
                        "index (" + index + ") is the size of the list."
            )
        }
        if (index > size) {
            throw IndexOutOfBoundsException(
                "Couldn't get the node: " +
                        "index (" + index + ") greater than the size of the " +
                        "list (" + size + ")."
            )
        }
        // Search the list and get the node
        var node: Node<E>
        if (index < size / 2) {
            // Search forwards
            node = header.next!!
            for (currentIndex in 0..<index) {
                node = node.next!!
            }
        } else {
            // Search backwards
            node = header
            for (currentIndex in size downTo index + 1) {
                node = node.previous!!
            }
        }
        return node
    }

    override fun hashCode(): Int {
        var hashCode = 1
        for (e in this) {
            hashCode = 31 * hashCode + (e?.hashCode() ?: 0)
        }
        return hashCode
    }

     override fun indexOf(element: E): Int {
        var i = 0
        var node = header.next!!
        while (node !== header) {
            if (isEqualValue(node.value, element)) {
                return i
            }
            i++
            node = node.next!!
        }
        return -1
    }

    /**
     * The equivalent of a default constructor, broken out so it can be called
     * by any constructor and by `readObject`.
     * Subclasses which override this method should make sure they call super,
     * so the list is initialized properly.
     */
    protected fun init() {
        header = createHeaderNode()
    }

    override fun isEmpty(): Boolean {
        return size == 0
    }

    /**
     * Compares two values for equals.
     * This implementation uses the equals method.
     * Subclasses can override this to match differently.
     *
     * @param value1  the first value to compare, may be null
     * @param value2  the second value to compare, may be null
     * @return true if equal
     */
    protected fun isEqualValue(value1: Any?, value2: Any?): Boolean {
        return equals(value1, value2)
    }

     override fun iterator(): MutableIterator<E> {
        return listIterator()
    }

     override fun lastIndexOf(element: E): Int {
        var i = size - 1
        var node = header.previous!!
        while (node !== header) {
            if (isEqualValue(node.value, element)) {
                return i
            }
            i--
            node = node.previous!!
        }
        return -1
    }

     override fun listIterator(): MutableListIterator<E> {
        return LinkedListIterator<E>(this, 0)
    }

     override fun listIterator(index: Int): MutableListIterator<E> {
        return LinkedListIterator<E>(this, index)
    }

     override fun removeAt(index: Int): E {
        val node = getNode(index, false)
        val oldValue = node.value
        removeNode(node)
        return oldValue!!
    }

     override fun remove(element: E): Boolean {
        var node = header.next!!
        while (node !== header) {
            if (isEqualValue(node.value, element)) {
                removeNode(node)
                return true
            }
            node = node.next!!
        }
        return false
    }

    /**
     * {@inheritDoc}
     *
     *
     * This implementation iterates over the elements of this list, checking each element in
     * turn to see if it's contained in `coll`. If it's contained, it's removed
     * from this list. As a consequence, it is advised to use a collection type for
     * `coll` that provides a fast (e.g. O(1)) implementation of
     * [Collection.contains].
     */
     override fun removeAll(coll: Collection<E>): Boolean {
        var modified = false
        val it = iterator()
        while (it.hasNext()) {
            if (coll.contains(it.next())) {
                it.remove()
                modified = true
            }
        }
        return modified
    }

    /**
     * Removes all nodes by resetting the circular list marker.
     */
    protected fun removeAllNodes() {
        header.next = header
        header.previous = header
        size = 0
        modCount++
    }

    /**
     * {@inheritDoc}
     */
    fun removeFirst(): E? {
        val node = header.next!!
        if (node === header) {
            throw NoSuchElementException()
        }
        val oldValue = node.value
        removeNode(node)
        return oldValue
    }

    /**
     * {@inheritDoc}
     */
    fun removeLast(): E? {
        val node= header.previous!!
        if (node === header) {
            throw NoSuchElementException()
        }
        val oldValue = node.value
        removeNode(node)
        return oldValue
    }

    /**
     * Removes the specified node from the list.
     *
     * @param node  the node to remove
     * @throws NullPointerException if `node` is null
     */
    protected fun removeNode(node: Node<E>) {
        node.previous!!.next = node.next
        node.next!!.previous = node.previous
        size--
        modCount++
    }

    /**
     * {@inheritDoc}
     *
     *
     * This implementation iterates over the elements of this list, checking each element in
     * turn to see if it's contained in `coll`. If it's not contained, it's removed
     * from this list. As a consequence, it is advised to use a collection type for
     * `coll` that provides a fast (e.g. O(1)) implementation of
     * [Collection.contains].
     */
    override fun retainAll(elements: Collection<E>): Boolean {
        var modified = false
        val it = iterator()
        while (it.hasNext()) {
            if (!elements.contains(it.next())) {
                it.remove()
                modified = true
            }
        }
        return modified
    }

     override fun set(index: Int, value: E): E {
        val node = getNode(index, false)
        val oldValue = node.value
        updateNode(node, value)
        return oldValue!!
    }

//     override fun size(): Int {
//        return size
//    }

    /**
     * Gets a sublist of the main list.
     *
     * @param fromIndexInclusive  the index to start from
     * @param toIndexExclusive  the index to end at
     * @return the new sublist
     */
     override fun subList(fromIndexInclusive: Int, toIndexExclusive: Int): MutableList<E> {
        return LinkedSubList(this, fromIndexInclusive, toIndexExclusive)
    }



//     override fun toArray(): Array<Any?> {
//        return toArray<Any?>(kotlin.arrayOfNulls<Any>(size))
//    }
//
//     override fun <T> toArray(array: Array<T>): Array<T> {
//        // Extend the array if needed
//        var array = array
//        if (array.size < size) {
//            val componentType: java.lang.Class<*>? = array.javaClass.getComponentType()
//            array = (kotlin.reflect.jvm.internal.impl.load.kotlin.JvmType.Array.newInstance(
//                componentType,
//                size
//            ) as kotlin.Array<T?>?)!!
//        }
//        // Copy the values into the array
//        var i = 0
//        var node: Node<E?> = header.next!!
//        while (node !== header) {
//            array[i] = node.value as T?
//            node = node.next!!
//            i++
//        }
//        // Set the value after the last value to null
//        if (array.size > size) {
//            array[size] = null
//        }
//        return array
//    }

    override fun toString(): String {
        if (isEmpty()) {
            return "[]"
        }
        val buf = StringBuilder(16 * size)
        buf.append("[")

        val it = iterator()
        var hasNext = it.hasNext()
        while (hasNext) {
            val value: Any? = it.next()
            buf.append(if (value === this) "(this Collection)" else value)
            hasNext = it.hasNext()
            if (hasNext) {
                buf.append(", ")
            }
        }
        buf.append("]")
        return buf.toString()
    }

    /**
     * Updates the node with a new value.
     * This implementation sets the value on the node.
     * Subclasses can override this to record the change.
     *
     * @param node  node to update
     * @param value  new value of the node
     */
    protected fun updateNode(node: Node<E>, value: E?) {
        node.value = value
    }
}
